1. Field of the Invention
This invention relates generally to interactive computing devices and, more specifically, to improved smooth curve generation techniques for use in conjunction with interactive computerized drawing systems.
2. Description of Prior Art
In many existing computerized drawing systems, a system user changes the position of a computer mouse or other pointing device on a substantially planar surface to create a drawing consisting of some combination of lines and curves. The drawing is displayed on some form of video display terminal, such as CRT display, an LCD display, or the like. The pointing device (i.e., the mouse) and the display are coupled to a computing device, such as a personal computer, a laptop computer, or the equivalent. The computer periodically samples the current position of the pointing device and uses these sampled position readings to plot the lines and curves drawn by the pointing device. The computing device cannot receive every point on the lines and curves, because the sampling interval is limited by the mouse. The plot is calculated by drawing straight lines between a plurality of successively sampled position readings of the mouse. Therefore, existing interactive curve drawing techniques utilize straight line segments between sample points, and these techniques do not interactively draw smooth curves.
Standard techniques for fitting smooth curves to a plurality of sampled position readings use higher-order polynomials. However, these approaches do not provide smooth curves in a user-interactive environment where the user would like to see lines and curves displayed as they are drawn, in real time. These techniques require a knowledge of position readings beyond the last sampled position of the pointing device. Since these position readings are unavailable until after the drawing has been completed, it is not possible to display smooth lines and curves in real time, as they are being drawn by the user.
In the example of FIG. 1, a system user has manipulated a pointing device (i.e., a computer mouse) to describe a substantially circular curve. The mouse position is periodically sampled, for example, at times t0, t1, t2, t3, t4, t5, t6, t7, and t8. At time t0, the mouse is at starting point P(0) 110; at time t1, the mouse is at point P(1) 101; at time t2, the mouse is at point P(2) 102; at time t3, the mouse is at point P(3) 103; at time t4, the mouse is at point P(4) 104; at time t5, the mouse is at point P(5) 105; at time t6, the mouse is at point P(6) 106; at time t7, the mouse is at point P(7) 107; and at time t8, the mouse is at point P(8) 108. Applying existing curve fitting methods to these sampled points in real time, as the sampled points are obtained, results in a curve 100 as shown in FIG. 1. Note that the curve 100 of FIG. 1 resembles a polygon, even though the user had manipulated the mouse in a circular manner.
A major shortcoming of existing curve plotting and curve drawing methods is that smooth curves cannot be drawn in a manner such that the effect of the most recently-sampled point is properly and fully considered. The curve that is drawn will lag the most currently sampled mouse position by at least one reading. The curves appear as if they consist of a plurality of line segments, when in fact a smooth arc was actually inscribed by the computer mouse. Using existing curve drawing and curve plotting methods, circular arcs appear as polygons, and curved arcs appear as a series of straight lines joined with sharp comers.
Smooth curves could be drawn if all of the sampled mouse positions were known beforehand, or if substantial parts of the curve were re-drawn every time the sampled mouse position changed. For example, using Bezier curves, once a new sampled mouse position point P(n) is taken, the entire curve must be recalculated (i.e., re-plotted or redrawn) from the starting point, i.e., P(0) 110. If B spline methods are used, once a new sampled mouse position point P(n) is taken, the future position of the mouse at sampled point P(n+1) must be known in order to draw a smooth curve. Therefore, using B spline methods, a smooth curve cannot be drawn in real time, as this curve is always one sampled point behind the most recently-sampled position of the mouse. This has been demonstrated to produce unacceptable results.
The mouse user expects to see a smooth curve on the video display terminal as the curve is traced by the computer mouse. What is needed is a method for interactively drawing (plotting) a smooth curve as each new sampled point is added to a sequence of sampled mouse positions, without any knowledge of the mouse position to be sampled next.